home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / snip9707.zip / SORTS.TXT < prev    next >
Text File  |  1997-07-05  |  3KB  |  55 lines

  1. +++Date last modified: 05-Jul-1997
  2.  
  3. There are four kinds of sorts.  There are sorts that search, sorts that swap,
  4. sorts that separate, and sorts that don't compare one element to another.  In
  5. the first class are the insertion sort, the extraction sort, and the heap
  6. sort. In the second class are the quick sort and the merge sort.  In the
  7. third class are the bubble sort and the Shell sort.  In the last class are
  8. the Radix-Exchange sort and the Pigeon sort.  (These lists aren't all
  9. inclusive. In fact, I know I'm leaving some sorts out, but I just want to
  10. give examples of what's in each class.)
  11.  
  12. I won't talk about the last class because I don't find them particularly
  13. interesting.  Even though they are the fastest kind of sorts known, with O(N)
  14. sorts not only possible but practical in many cases, it is difficult to
  15. generalize them, and I'm fond of finding general solutions to general
  16. problems.
  17.  
  18. In the sorts that swap, the only variable is which elements are swapped.  The
  19. Shell sort starts by swapping elements that are far apart in hopes that any
  20. "large scale" disorder is eliminated quickly.  The bubble sort compares only
  21. those elements that are next to each other.  Each pair is compared and, if
  22. they are found to be out of order, they are swapped.
  23.  
  24. The sorts that separate work by understanding that it is a lot faster to sort
  25. smaller lists than bigger lists.  So, you seek to break up the lists into
  26. halves and then break up the halves and then break up the quarters, and so on
  27. until each piece is small enough to sort.  (Often, a program will just
  28. continue to break the list down until each piece has a length of one.  A list
  29. of one item is already sorted.  On the other hand, many programmers prefer to
  30. stop after the element size gets small enough.)
  31.  
  32. However, there is a choice to be made in this case.  Do you attempt to impose
  33. order on the list before or after you split it into parts.  The quick sort is
  34. a before sort.  The merge sort is an after sort.  When you quick sort a list,
  35. you choose a value, called the pivot, and you build your sublists such that
  36. all of the elements which have a key value less than the pivot go into one
  37. sublist and those elements which do not go into the other.  Then, you
  38. recursively sort each sublist and when that is done you simply append the
  39. "greater than" list to the "less than" list to make the whole sorted list.
  40. With a merge sort, you find the middle and break it there without any concern
  41. for the key values of the elements, recursively sort each sublist and then
  42. merge the two sorted lists back together into one big list.  (The real nice
  43. thing about the merge sort is you don't have to be able to pick a good pivot
  44. value in order for it to work well. Most of the algorithms for finding the
  45. best pivot values start "Sort the list...")
  46.  
  47. The insertion sort is what you do when you "build a sorted list."  Basically,
  48. you go through the unsorted list, and for each element, you find the place in
  49. the sorted list where it should go and put it there.  This process is
  50. repeated until there are no more elements in the unsorted list. The
  51. extraction sort looks through the unsorted list for the element with the
  52. biggest (or smallest) value and once it finds it, appends that element to the
  53. sorted list.  This process is repeated until there are no more elements in
  54. the unsorted list.
  55.